<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html>
<head>
<!-- Copyright 1997 The Open Group, All Rights Reserved -->
<title>yacc</title>
</head><body bgcolor=white>
<center>
<font size=2>
The Single UNIX &reg; Specification, Version 2<br>
Copyright &copy; 1997 The Open Group

</font></center><hr size=2 noshade>
<h4><a name = "tag_001_014_2942">&nbsp;</a>NAME</h4><blockquote>
yacc - yet another compiler compiler (<b>DEVELOPMENT</b>)
</blockquote><h4><a name = "tag_001_014_2943">&nbsp;</a>SYNOPSIS</h4><blockquote>
<pre><code>

yacc <b>[</b>-dltv<b>][</b>-b <i>file_prefix</i><b>][</b>-p <i>sym_prefix</i><b>]</b><i> grammar</i>
</code>
</pre>
</blockquote><h4><a name = "tag_001_014_2944">&nbsp;</a>DESCRIPTION</h4><blockquote>
<p>
The
<i>yacc</i>
utility reads a description of a context-free grammar in
<i>file</i>
and writes
C source code, conforming to the ISO&nbsp;C standard,
to a code file, and optionally
header information into a header file,
in the current directory.
The C code defines a function and related routines and macros
for an automaton that executes a parsing algorithm meeting the requirements in
<xref href=yaccalg><a href="#tag_001_014_2954_013">
Algorithms
</a></xref>.
<p>
The form and meaning of the grammar are described in the
EXTENDED DESCRIPTION section.
<p>
The C source code and header file are produced in a form
suitable as input for the C compiler (see
<i><a href="c89.html">c89</a></i>).
</blockquote><h4><a name = "tag_001_014_2945">&nbsp;</a>OPTIONS</h4><blockquote>
The
<i>yacc</i>
utility supports the <b>XBD</b> specification, <a href="../xbd/utilconv.html#usg"><b>Utility Syntax Guidelines</b>&nbsp;</a> .
<p>
The following options are supported:
<dl compact>

<dt><b>-b&nbsp;</b><i>file_prefix</i>
<dd>
Use
<i>file_prefix</i>
instead of
y
as the prefix for all output filenames.
The code file
<b>y.tab.c</b>,
the header file
<b>y.tab.h</b>
(created when
<b>-d</b>
is specified),
and the description file
<b>y.output</b>
(created when
<b>-v</b>
is specified),
will be changed to
<i>file_prefix</i><b>.tab.c</b>,
<i>file_prefix</i><b>.tab.h</b>,
and
<i>file_prefix</i><b>.output</b>,
respectively.

<dt><b>-d</b>
<dd>Write the header file;
by default only the code file is written.
The
<b>#define</b>
statements that associate the
token codes assigned by
<i>yacc</i>
with the user-declared token names.
This allows source files other than
<b>y.tab.c</b>
to access the token codes.

<dt><b>-l</b>
<dd>Produce a code file that does not contain any
<b>#line</b>
constructs.
If this option is not present, it is unspecified whether the
code file or header file contains
<b>#line</b>
directives.
This should only be used after the
grammar and the associated actions are fully debugged.

<dt><b>-p&nbsp;</b><i>sym_prefix</i>
<dd>
Use
<i>sym_prefix</i>
instead of
yy
as the prefix for all external names produced by
<i>yacc</i>.
The names affected include the functions
<i>yyparse()</i>,
<i>yylex()</i>
and
<i>yyerror()</i>,
and the variables
<i>yylval</i>,
<i>yychar</i>
and
<i>yydebug</i>.
(In the remainder of this section, the six symbols cited
are referenced using their default names only as a notational convenience.)
Local names may also be affected by the
<b>-p</b>
option;
however, the
<b>-p</b>
option does not affect
<b>#define</b>
symbols generated by
<i>yacc</i>.

<dt><b>-t</b>
<dd>Modify conditional compilation directives to permit compilation
of debugging code in the code file.
Run-time debugging statements
will be always contained in the code file,
but by default conditional
compilation directives prevent their compilation.

<dt><b>-v</b>
<dd>Write a file containing a description of the parser and a report
of conflicts generated by ambiguities in the grammar.

</dl>
<br>
</blockquote><h4><a name = "tag_001_014_2946">&nbsp;</a>OPERANDS</h4><blockquote>
The following operand is required:
<dl compact>

<dt><i>grammar</i><dd>
A pathname of a file containing instructions, hereafter called
<i>grammar ,</i>
for which a parser is to be created.
The format for the grammar is described in the
EXTENDED DESCRIPTION section.

</dl>
</blockquote><h4><a name = "tag_001_014_2947">&nbsp;</a>STDIN</h4><blockquote>
Not used.
</blockquote><h4><a name = "tag_001_014_2948">&nbsp;</a>INPUT FILES</h4><blockquote>
The file
<i>grammar</i>
must be a text file formatted as specified in the
EXTENDED DESCRIPTION section.
</blockquote><h4><a name = "tag_001_014_2949">&nbsp;</a>ENVIRONMENT VARIABLES</h4><blockquote>
The following environment variables affect the execution of
<i>yacc</i>:
<dl compact>

<dt><i>LANG</i><dd>Provide a default value for the internationalisation variables
that are unset or null.
If
<i>LANG</i>
is unset or null, the corresponding value from the
implementation-dependent default locale will be used.
If any of the internationalisation variables contains an invalid setting, the
utility will behave as if none of the variables had been defined.

<dt><i>LC_ALL</i><dd>
If set to a non-empty string value,
override the values of all the other internationalisation variables.

<dt><i>LC_CTYPE</i><dd>
Determine the
locale for the interpretation of sequences of bytes of text data as
characters (for example, single- as opposed to multi-byte characters
in arguments and input files).

<dt><i>LC_MESSAGES</i><dd>
Determine the locale that should be used to affect
the format and contents of diagnostic
messages written to standard error.

<dt><i>NLSPATH</i><dd>
Determine the location of message catalogues
for the processing of
<i>LC_MESSAGES .
</i>
</dl>
<p>
The
<i>LANG</i>
and
<i>LC_*</i>
variables affect the execution of the
<i>yacc</i>
utility as stated.
The
<i>main()</i>
function defined in
<xref href=yacclib><a href="#tag_001_014_2954_011">
Yacc Library
</a></xref>
calls:
<pre>
<code>
setlocale(LC_ALL, "")
</code>
</pre>
and thus, the program generated by
<i>yacc</i>
will also be affected by the
contents of these variables at runtime.
</blockquote><h4><a name = "tag_001_014_2950">&nbsp;</a>ASYNCHRONOUS EVENTS</h4><blockquote>
Default.
</blockquote><h4><a name = "tag_001_014_2951">&nbsp;</a>STDOUT</h4><blockquote>
Not used.
</blockquote><h4><a name = "tag_001_014_2952">&nbsp;</a>STDERR</h4><blockquote>
If shift/reduce or reduce/reduce conflicts
are detected in
<i>grammar</i>,
<i>yacc</i>
writes a report of those conflicts to the standard error
in an unspecified format.
<p>
Standard error is also used for diagnostic messages.
</blockquote><h4><a name = "tag_001_014_2953">&nbsp;</a>OUTPUT FILES</h4><blockquote>
The code file, the header file and
the description file are text files.
All are described in the following sections.
<h5><a name = "tag_001_014_2953_001">&nbsp;</a>Code file</h5>
This file will contain the C source code for the
<i>yyparse()</i>
routine.
It will contain code for the various semantic actions with macro
substitution performed on them as described in the
EXTENDED DESCRIPTION section.
It will also contain a copy of the
<b>#define</b>
statements in the header file.
If a
<b>%union</b>
declaration is used, the declaration for YYSTYPE
also will be included in this file.
<p>
The contents of the Program Section (see
<xref href=yaccprog><a href="#tag_001_014_2954_005">
Programs Section
</a></xref>)
of the input file will then be included.
<h5><a name = "tag_001_014_2953_002">&nbsp;</a>Header file</h5>
The header file will contain
<b>#define</b>
statements that associate the
token numbers with the token names.
This allows source files other than
the code file
to access the token codes.
If a
<b>%union</b>
declaration is used, the declaration for
YYSTYPE
and an
extern YYSTYPE yylval
declaration also will be included in this file.
<h5><a name = "tag_001_014_2953_003">&nbsp;</a>Description file</h5>
The description file
will be a text file containing a description of the state machine
corresponding to the parser, using an unspecified format.
Limits for internal tables (see
<b>Limits</b>
in the EXTENDED DESCRIPTION section)
will also be reported, in an implementation-dependent manner.
(Some implementations may use dynamic allocation techniques
and have no specific limit values to report.)
</blockquote><h4><a name = "tag_001_014_2954">&nbsp;</a>EXTENDED DESCRIPTION</h4><blockquote>
The
<i>yacc</i>
command accepts a language that is used to define a grammar for a target
language to be parsed by the tables and code generated by
<i>yacc</i>.
The language
accepted by
<i>yacc</i>
as a grammar for the target language is described below using the
<i>yacc</i>
input language itself.
<p>
The input
<i>grammar</i>
includes rules describing the input structure of the target language
and code to be invoked when these rules are recognised to provide
the associated semantic action.
The code to be executed will appear as bodies of text
that are intended to be C-language code.
The C-language inclusions are presumed to form a correct function
when processed by
<i>yacc</i>
into its output files.
The code included in this way will be executed
during the recognition of the target language.
<p>
Given a grammar, the
<i>yacc</i>
utility generates the files described in the OUTPUT FILES section.
The code file can be compiled and linked using
<i><a href="cc.html">cc</a></i>
or
<i><a href="c89.html">c89</a></i>.
If the declaration
and programs sections of the grammar file did not include
definitions of
<i>main()</i>,
<i>yylex()</i>
and
<i>yyerror()</i>,
the compiled output requires linking with externally supplied
version of those functions.
Default versions of
<i>main()</i>
and
<i>yyerror()</i>
are supplied in the
<i>yacc</i>
library and can be linked in by using the
<b>-l&nbsp;y</b>
operand to
<i><a href="cc.html">cc</a></i>
or
<i><a href="c89.html">c89</a></i>.
The
<i>yacc</i>
library interfaces need not support
interfaces with other than the default
<b>yy</b>
symbol prefix.
The application provides the lexical analyser function,
<i>yylex()</i>;
the
<i><a href="lex.html">lex</a></i>
utility
is specifically designed to generate such a routine.
<h5><a name = "tag_001_014_2954_001">&nbsp;</a>Input Language</h5>
Every specification file must consist of three sections
in order:
<i>declarations ,</i>
<i>grammar rules</i>
and
<i>programs ,</i>
separated by double percent signs
(<b>%%</b>).
The declarations and programs sections can be empty.
If the latter is empty, the preceding
<b>%%</b>
mark separating it from the rules section can be omitted.
<p>
The input is free form text following the structure of the
grammar defined below.
<h5><a name = "tag_001_014_2954_002">&nbsp;</a>Lexical Structure of the Grammar</h5>
<xref type="5" name="yacclex"></xref>
The characters
blank,
newline
and
form-feed
are ignored, except that they must not appear
in names or multi-character reserved symbols.
Comments must be enclosed in
/*&nbsp;...\ */,
and can appear wherever a name is valid.
<p>
Names are of arbitrary length, made up of letters, periods
(.),
underscores
(_)
and non-initial digits.
Upper- and lower-case letters are distinct.
Portable applications must not use
names beginning in
yy
or
YY
since the
<i>yacc</i>
parser uses such names.
Many of the names appear in the final output of
<i>yacc</i>,
and thus they should be chosen to conform with any additional rules
created by the C compiler to be used.
In particular they will appear
in
<b>#define</b>
statements.
<p>
A literal consists of a single character enclosed in single-quotes
(').
All of the escape sequences supported for character constants
by the ISO&nbsp;C standard are supported by
<i>yacc</i>.
<p>
The relationship with the lexical analyser is discussed in detail below.
<p>
The NUL character must not be used in grammar rules or literals.
<h5><a name = "tag_001_014_2954_003">&nbsp;</a>Declarations Section</h5>
<xref type="5" name="yaccdecl"></xref>
The declarations section is used to define the symbols used to define
the target language and their relationship with each other.
In particular,
much of the additional information required to resolve ambiguities in
the context-free grammar for the
target language is provided here.
<p>
Usually
<i>yacc</i>
assigns the relationship between the symbolic names it generates and
their underlying numeric value.
The declarations section makes it
possible to control the assignment of these values.
<p>
It is also possible to keep semantic information associated with
the tokens currently on the parse stack in a user-defined C-language
<b>union</b>,
if the members of the union are associated with the various names
in the grammar.
The declarations section provides for this as well.
<p>
The first group of declarators below all take a list of names as arguments.
That list can optionally be preceded by
the name of a C union member (called a
<i>tag</i>
below) appearing within "&lt;" and "&gt;".
(As an exception to the typographical conventions
of the rest of this specification, in this case
&lt;<i>tag</i>&gt;
does not represent a metavariable,
but the literal angle bracket characters surrounding a symbol.)
The use of
<i>tag</i>
specifies that the tokens named on this line
are to be of the same C type as the
union member referenced by
<i>tag</i>.
This is discussed in more detail below.
<p>
For lists used to define tokens, the first appearance of
a given token can be followed by a
positive integer (as a string of decimal digits).
If this is done, the underlying value assigned to it for lexical purposes
will be taken to be that number.
<dl compact>

<dt>%token <b>[</b>&lt;<i>tag</i>&gt;<b>] </b><i>name </i><b>[</b><i>number</i><b>] [</b><i>name </i><b>[</b><i>number</i><b>]]</b>...<dd>
Declares
<i>name</i>s
to be a token.
If
<i>tag</i>
is present, the C type for all tokens on this line will be declared
to be the type referenced by
<i>tag</i>.
If a positive integer,
<i>number</i>,
follows a
<i>name</i>,
that value will be assigned to the token.

<dt>%left <b>[</b>&lt;<i>tag</i>&gt;<b>] </b><i>name </i><b>[</b><i>number</i><b>] [</b><i>name </i><b>[</b><i>number</i><b>]]</b>...<dd>
<dt>%right <b>[</b>&lt;<i>tag</i>&gt;<b>] </b><i>name </i><b>[</b><i>number</i><b>] [</b><i>name </i><b>[</b><i>number</i><b>]]</b>...<dd>
Declares
<i>name</i>
to be a token, and assigns precedence to it.
One or more lines, each beginning with one of these symbols,
can appear in this section.
All tokens on the same line have the same precedence level and
associativity; the lines are in order of increasing precedence or binding
strength.
<b>%left</b>
denotes that the operators on that line are left associative, and
<b>%right</b>
similarly denotes right associative operators.
If
<i>tag</i>
is present, it declares a C type for
<i>name</i>s
as described for
<b>%token</b>.


<dt>%nonassoc <b>[</b>&lt;<i>tag</i>&gt;<b>] </b><i>name </i><b>[</b><i>number</i><b>] [</b><i>name </i><b>[</b><i>number</i><b>]]</b>...<dd>
Declares
<i>name</i>
to be a token, and indicates that this
cannot be used associatively.
If the parser encounters associative use of this token
it will report an error.
If
<i>tag</i>
is present, it declares a C type for
<i>name</i>s
as described for
<b>%token</b>.

<dt>%type <b>[</b>&lt;<i>tag</i>&gt;<b>] </b><i>name</i>...<dd>
Declares that union member
<i>name</i>s
are non-terminals,
and thus it is required to have a
<i>tag</i>
field at its beginning.
Because it deals with non-terminals only,
assigning a token number or using a literal is also prohibited.
If this construct is present,
<i>yacc</i>
will perform type checking;
if this construct is not present, the parse stack will hold only the
<b>int</b>
type.

</dl>
<p>
Every name used in
<i>grammar</i>
undefined by a
<b>%token</b>,
<b>%left</b>,
<b>%right</b>
or
<b>%nonassoc</b>
declaration is assumed to represent a non-terminal symbol.
The
<i>yacc</i>
utility will report an error for any non-terminal symbol that
does not appear on the left side of at least one grammar rule.
<p>
Once the type, precedence or token number of a name is specified,
it will not be changed.
If the first declaration of a token does not
assign a token number,
<i>yacc</i>
will assign a token number.
Once this assignment is made, the token number will not be changed
by explicit assignment.
<p>
The following declarators do not follow the previous pattern.
<dl compact>

<dt>%start<dd>
Declares the non-terminal
<i>name</i>
to be the
<i>start symbol ,</i>
which represents the largest, most general structure
described by the grammar rules.
By default, it is the left-hand side of the first grammar rule; this
default can be overridden with this declaration.

<dt>%union {<i> body of union (in C) </i>}<dd>
Declares the
<i>yacc</i>
value stack to be a union of the various types
of values desired.
By default, the values returned by actions (see below) and the lexical
analyser will be integers.
The
<i>yacc</i>
utility keeps track of types, and will insert corresponding union member
names in order to perform strict type checking of the resulting parser.

Alternatively,
given that at least one <b>&lt;</b><i>tag</i><b>&gt;</b>
construct is used,
the union can be declared in a header file
(which will be included in the declarations section by using
an
#include
construct within
<b>%{</b>
and
<b>%}</b>),
and a
<b>typedef</b>
used to define the symbol
YYSTYPE
to represent this union.
The effect of
<b>%union</b>
is to provide the declaration of
YYSTYPE
directly from the
input.

<dt>%{ ... %}<dd>
C-language declarations and definitions can appear in the
declarations section,
enclosed by these marks.
These statements will be copied into the
code file, and have global scope
within it so that they can be used
in the rules and program sections.

</dl>
<p>
The declarations section must be terminated by the token
<b>%%</b>.
<h5><a name = "tag_001_014_2954_004">&nbsp;</a>Grammar Rules in yacc</h5>
<xref type="5" name="yaccgram"></xref>
The rules section defines the context-free grammar to be accepted by
the function
<i>yacc</i>
generates, and associates with those rules C-language actions and
additional precedence information.
The grammar is described below,
and a formal definition follows.
<p>
The rules section is comprised of one or more grammar rules.
A grammar rule has the form:
<pre>
<code>
A : BODY ;
</code>
</pre>
<p>
The symbol
A
represents a non-terminal name, and
<b>BODY</b>
represents a sequence of zero or more
<i>name</i>s,
<i>literal</i>s
and
<i>semantic action</i>s
that can then be
followed by optional
<i>precedence rule</i>s.
Only the names and literals
participate in the formation of the grammar; the semantic actions and
precedence rules are used in other ways.
The colon and the semicolon are
<i>yacc</i>
punctuation.
If there are several successive grammar rules with the same left-hand side,
the vertical bar "|"
can be used to avoid rewriting the left-hand side;
in this case the semicolon appears only after the last rule.
The
BODY
part can be empty (or empty of names and literals) to indicate that the
non-terminal symbol matches
the empty string.
<p>
The
<i>yacc</i>
utility assigns a unique number to each rule.
Rules using the vertical bar notation are distinct rules.
The number assigned to the rule appears in the description file.
<p>
The elements comprising a BODY are:
<dl compact>

<dt><i>name</i><dd>
<dt><i>literal</i><dd>These form the rules of the grammar:
<i>name</i>
is either a
<i>token</i>
or a
<i>non-terminal</i>;
<i>literal</i>
stands for itself (less the lexically required quotation marks).

<dt><i>semantic action</i><dd>
With each grammar rule, the user can associate actions to be performed
each time the rule is recognised in the input process.
(Note that the word &quot;action&quot; can also refer to the actions of the
parsershift, reduce, and so on.)

These actions can return values and can obtain the values returned by
previous actions.
These values will be kept in objects of type YYSTYPE (see
<b>%union</b>).
The result value of the action will be kept on the parse stack with the
left-hand side of the rule, to be accessed by other reductions
as part of their right-hand side.
By using the
&lt;<i>tag</i>&gt;
information provided in the declarations section, the code generated by
<i>yacc</i>
can be strictly type checked and contain arbitrary information.
In addition, the lexical analyser can provide the same kinds of
values for tokens, if desired.

An action is an arbitrary C statement and as such can do input or output,
call subprograms and alter external variables.
An action is one or more C statements enclosed in curly braces
"{"
and
"}".

Certain pseudo-variables can be used in the action.
These are
macros for access to data structures known internally to
<i>yacc</i>.
<dl compact>

<dt><b>$$</b><dd>The value of the action can be set by assigning it to
$$.
If type checking is enabled and
the type of the value to be assigned cannot be determined,
a diagnostic message may be generated.

<dt><b>$</b><i>number</i><dd>This refers to the value returned by the component specified by
the token
<i>number</i>
in the right side of a rule, reading from left to right;
<i>number</i>
can be zero or negative.
If it is, it refers to the data
associated with the name
on the parser's stack preceding the leftmost symbol of the current rule.
(That is,
$0
refers to the name immediately preceding the leftmost name in the
current rule, to be found on the parser's stack and
$-1
refers to the
symbol to
<i>its</i>
left.)
If
<i>number</i>
refers to an element past the current point in the rule, or beyond the
bottom of the stack, the result is undefined.
If type checking is enabled and
the type of the value to be assigned cannot be determined,
a diagnostic message may be generated.

<dt><b>$</b><i>&lt;tag&gt;number</i><dd>
These correspond exactly to the corresponding symbols without the
<i>tag</i>
inclusion, but allow for strict type checking (and preclude unwanted
type conversions).
The effect is that the macro is
expanded to use
<i>tag</i>
to select an element from the
YYSTYPE
union (using
<i>dataname.tag</i>).
This is particularly useful if
<i>number</i>
is not positive.

<dt><b>$</b><i>&lt;tag&gt;</i><b>$</b><dd>This imposes on the reference the type of the union member
referenced by
<i>tag</i>.
This construction is applicable when
a reference to a left context value occurs in the grammar,
and provides
<i>yacc</i>
with a means for selecting a type.

</dl>
<p>
Actions can occur in the middle of a rule as well as at
the end; an action can access values returned by actions
to its left, and in turn the value it returns can be accessed
by actions to its right.
An action appearing in the middle
of a rule will be equivalent to replacing the action with a new
non-terminal symbol and adding an empty rule with that
non-terminal symbol on the left-hand side.
The semantic action associated with the new rule will be
equivalent to the original action.
The use of actions within rules might
introduce conflicts that would not otherwise exist.
<p>
By default, the value of a rule is the value of the first element in it.
If the first element does not have a type (particularly in the case of
a literal) and type checking is turned on by
<b>%type</b>
an error message will result.
<p>
<dt><i>precedence</i><dd>
The keyword
<b>%prec</b>
can be used to change the precedence level associated with
a particular grammar rule.
Examples of this are
in cases where a unary and binary operator have the same symbolic
representation, but need to be given different precedences,
or where the handling of an ambiguous if-else construction
is necessary.
The reserved symbol
<b>%prec</b>
can appear immediately after the body of the grammar rule
and can be followed by a token name or a literal.
It will cause the precedence of the grammar rule to become that of the
following token name or literal.
The action for the rule as a whole can follow
<b>%prec</b>.
<p>
</dl>
<p>
If a program section follows, the grammar rules must be terminated by
<b>%%</b>.
<h5><a name = "tag_001_014_2954_005">&nbsp;</a>Programs Section</h5>
<xref type="5" name="yaccprog"></xref>
The <i>programs</i> section can
include the definition of the lexical analyser
<i>yylex()</i>,
and any other functions, for example those used in the
actions specified in the grammar rules.
This is C-language code, and will be included in
the code file after the tables and code generated by
<i>yacc</i>.
It is unspecified whether the programs section precedes or follows
the semantic actions in the output file; therefore,
if the application contains any macro definitions
and declarations intended to apply to the code in the semantic actions,
it must place them within
<b>%{...%}</b>
in the declarations section.
<h5><a name = "tag_001_014_2954_006">&nbsp;</a>Input Grammar</h5>
The following input to
<i>yacc</i>
yields a parser for the input to
<i>yacc</i>.
This formal syntax takes precedence over
the preceding text syntax description.
<p>
The lexical structure is defined less precisely;
<xref href=yacclex><a href="#tag_001_014_2954_002">
Lexical Structure of the Grammar
</a></xref>
defines most terms.
The correspondence
between the previous terms and the tokens below is as follows.
<dl compact>

<dt><b>IDENTIFIER</b><dd>
This corresponds to the concept of
<i>name</i>,
given previously.
It also includes literals as defined previously.

<dt><b>C_IDENTIFIER</b><dd>
This is a name, and additionally it is known to be followed by a colon.
A literal cannot yield this token.

<dt><b>NUMBER</b><dd>
A string of digits (a non-negative decimal integer).

<dt><b>TYPE</b><dd>
<dt><b>LEFT</b><dd>
<dt><b>MARK</b><dd>
<dt>and so on<dd>
These correspond directly to
<b>%type</b>,
<b>%left</b>,
<b>%%</b>
and so on.

<dt><b>{ </b>...<b> }</b><dd>This indicates C-language source code, with the possible inclusion of
"$" macros as discussed previously.

</dl>
<pre>
<code>
/* Grammar for the input to yacc */
/* Basic entries */
/* The following are recognised by the lexical analyser */

%token    IDENTIFIER      /* includes identifiers and literals */
%token    C_IDENTIFIER    /* identifier (but not literal)
                             followed by a : */
%token    NUMBER          /* [0-9][0-9]* */

/* Reserved words : %type=&gt;TYPE %left=&gt;LEFT, and so on */

%token    LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION

%token    MARK            /* the %% mark */
%token    LCURL           /* the %{ mark */
%token    RCURL           /* the }% mark */

/* 8-bit character literals stand for themselves; */
/* tokens have to be defined for multi-byte characters */

%start    spec

%%

spec  :    defs MARK rules tail
      ;
tail  : MARK
      {
        /* In this action, set up the rest of the file */
      }
      | /* empty; the second MARK is optional */
      ;
defs  : /* empty */
      |    defs def
      ;
def   : START IDENTIFIER
      |    UNION
      {
        /* Copy union definition to output */
      }
      |    LCURL
      {
        /* Copy C code to output file */
      }
        RCURL
      |    rword tag nlist
      ;
rword : TOKEN
      | LEFT
      | RIGHT
      | NONASSOC
      | TYPE
      ;
tag   : /* empty: union tag id optional */
      | '&lt;' IDENTIFIER '&gt;'
      ;
nlist : nmno
      | nlist nmno
      ;
nmno  : IDENTIFIER         /* Note: literal invalid with % type */
      | IDENTIFIER NUMBER  /* Note: invalid with % type */
      ;

/* rule section */

rules : C_IDENTIFIER rbody prec
      | rules  rule
      ;
rule  : C_IDENTIFIER rbody prec
      | '|' rbody prec
      ;
rbody : /* empty */
      | rbody IDENTIFIER
      | rbody act
      ;
act   : '{'
        {
          /* Copy action, translate $$, and so on */
        }
        '}'
      ;
prec  : /* empty */
      | PREC IDENTIFIER
      | PREC IDENTIFIER act
      | prec ';'
      ;
</code>
</pre>
<h5><a name = "tag_001_014_2954_007">&nbsp;</a>Conflicts</h5>
The parser produced for an input grammar may contain states in
which conflicts occur.
The conflicts occur because the grammar is not LALR(1).
An ambiguous grammar always contains at least one LALR(1) conflict.
The
<i>yacc</i>
utility will resolve all conflicts, using either
default rules or user-specified precedence rules.
<p>
Conflicts are either shift/reduce conflicts
or reduce/reduce conflicts.
A shift/reduce conflict is where, for a given state
and lookahead symbol, both a shift action and a reduce action are possible.
A reduce/reduce conflict is where, for a given state and
lookahead symbol, reductions by two different rules are possible.
<p>
The rules below describe how to specify what
actions to take when a conflict occurs.
Not all shift/reduce conflicts
can be successfully resolved this way because the conflict may be due to
something other than ambiguity, so incautious use of these facilities
can cause the language accepted by the parser to be much different from
that which was intended.
The description file
will contain sufficient information to understand the cause of the conflict.
Where ambiguity is the reason either the default or explicit rules
should be adequate to produce a working parser.
<p>
The declared precedences and associativities (see
<xref href=yaccdecl><a href="#tag_001_014_2954_003">
Declarations Section
</a></xref>)
are used to resolve parsing conflicts as follows:
<ol>
<p>
<li>
A precedence and associativity is associated with each grammar rule; it is
the precedence and associativity of the last token or literal in the body
of the rule.
If the
<b>%prec</b>
keyword is used, it overrides this default.
Some grammar rules might not have both precedence and associativity.
<p>
<li>
If there is a shift/reduce conflict, and
both the grammar rule and the input symbol
have precedence and associativity associated
with them, then the conflict is resolved in
favour of the action (shift or reduce) associated
with the higher precedence.
If the precedences are the same, then the associativity is used;
left associative implies reduce,
right associative implies shift,
and non-associative implies an error in the string being parsed.
<p>
<li>
When there is a shift/reduce conflict that
cannot be resolved by rule 2,
the shift is done.
Conflicts resolved this way are
counted in the diagnostic output described
in
<xref href=yaccerr><a href="#tag_001_014_2954_008">
Error Handling
</a></xref>.
<p>
<li>
When there is a reduce/reduce conflict, a
reduction is done by the grammar rule that
occurs earlier in the input sequence.
Conflicts resolved this way are counted in the
diagnostic output described in
<xref href=yaccerr><a href="#tag_001_014_2954_008">
Error Handling
</a></xref>.
<p>
</ol>
<p>
Conflicts resolved by precedence
or associativity will not be counted in the shift/reduce and
reduce/reduce conflicts reported by
<i>yacc</i>
on either standard error or in
the description file.
<br>
<h5><a name = "tag_001_014_2954_008">&nbsp;</a>Error Handling</h5>
<xref type="5" name="yaccerr"></xref>
The token
<b>error</b>
is reserved for error handling.
The name
<b>error</b>
can be used in grammar rules.
It indicates places where the parser can recover from a syntax error.
The default value of
<b>error</b>
is 256.
Its value can be changed using a
<b>%token</b>
declaration.
The lexical analyser should not return the value of
<b>error</b>.
(Multi-byte characters should be recognised by
the lexical analyser and returned as tokens.
They should not be returned as multi-byte character literals.
The token
<b>error</b>
that is used for error recovery is normally assigned
the value 256 in the historical implementation.
Thus, the token value 256, which used in many
multi-byte character sets, is not available for
use as the value of a user-defined token.)
<p>
The parser will detect a syntax error when it is in a
state where the action associated with the lookahead symbol is
<b>error</b>.
A semantic action can cause the
parser to initiate error handling by executing the macro YYERROR.
When YYERROR
is executed, the semantic action will pass control back to the parser.
YYERROR cannot be used outside of semantic actions.
<p>
When the parser detects a syntax error, it normally calls
<b>yyerror</b>
with the character string
syntax&nbsp;error
as its argument.
The call will not be made if the parser
is still recovering from a previous error when the
error is detected.
The parser is considered to be
recovering from a previous error until the parser
has shifted over at least three normal input symbols
since the last error was detected or a semantic action
has executed the macro
<b>yyerrok</b>.
The parser will not call
<b>yyerror</b>
when YYERROR is executed.
<p>
The macro function YYRECOVERING() will return 1 if a syntax error has
been detected and the parser has not yet fully recovered from it.
Otherwise, zero will be returned.
<p>
When a syntax error is detected by the parser, the
parser will check if a previous syntax error has been detected.
If a previous error was detected, and if
no normal input symbols have been shifted since the
preceding error was detected, the parser checks if
the lookahead symbol is an endmarker (see
<xref href=yaccilex><a href="#tag_001_014_2954_009">
Interface to the Lexical Analyser
</a></xref>).
If it is, the parser will return with a non-zero value.
Otherwise, the lookahead symbol will be
discarded and normal parsing will resume.
<p>
When YYERROR is executed or when the parser detects
a syntax error and no previous error has been detected,
or at least one normal input symbol has been shifted
since the previous error was detected, the parser
will pop back one state at a time until the parse stack
is empty or the current state allows a shift over
<b>error</b>.
If the parser empties the parse stack, it
will return with a non-zero value.
Otherwise, it will shift over
<b>error</b>
and then resume normal parsing.
If the parser reads a lookahead symbol before the error
was detected, that symbol will still be the lookahead
symbol when parsing is resumed.
<p>
The macro
<b>yyerrok</b>
in a semantic action will cause the
parser to act as if it has fully recovered from any
previous errors.
The macro
<b>yyclearin</b>
will cause the parser to discard the current lookahead token.
If the current lookahead token has not yet been read,
<b>yyclearin</b>
will have no effect.
<p>
The macro YYACCEPT will cause the parser to return with the value zero.
The macro YYABORT will cause the parser to return with a non-zero value.
<h5><a name = "tag_001_014_2954_009">&nbsp;</a>Interface to the Lexical Analyser</h5>
<xref type="5" name="yaccilex"></xref>
The
<i>yylex()</i>
function is an integer-valued function that returns a
<i>token number</i>
representing the kind of token read.
If there is a value associated with the token returned by
<i>yylex()</i>
(see the discussion of
<i>tag</i>
above), it will be assigned to
the external variable
<i>yylval</i>.
<p>
If the parser and
<i>yylex()</i>
do not agree on these token numbers,
reliable communication between them cannot occur.
For (one character) literals, the token is simply the numeric
value of the character in the current character set.
The numbers for other tokens can either be chosen by
<i>yacc</i>,
or chosen by the user.
In either case, the
<b>#define</b>
construct of C is used to allow
<i>yylex()</i>
to return these numbers symbolically.
The
<b>#define</b>
statements are put into
the code file, and the header file
if that file is requested.
The set of characters permitted by
<i>yacc</i>
in an identifier is larger
than that permitted by C.
Token names found to contain such characters
will not be included in the
<b>#define</b>
declarations.
<p>
If the token numbers are chosen by
<i>yacc</i>,
the tokens other than literals will be assigned
numbers greater than 256,
although no order is implied.
A token can be explicitly assigned a number by following
its first appearance in the
declarations section with a number.
Names and literals not defined this way retain their default definition.
All assigned token numbers will be unique and distinct from the
token numbers used for literals.
If duplicate token numbers
cause conflicts in parser generation,
<i>yacc</i>
will report an error;
otherwise, it is unspecified whether the token assignment is
accepted or an error is reported.
<p>
The end of the input is marked by a special token called the
<i>endmarker ,</i>
which has a token number that is zero or negative.
(These values are invalid for any other token.)
All lexical analysers will return zero or negative as a token number
upon reaching the end of their input.
If the tokens up to, but excluding, the endmarker form a structure that
matches the start symbol, the parser will accept the input.
If the endmarker is seen in any other context, it will be considered an error.
<h5><a name = "tag_001_014_2954_010">&nbsp;</a>Completing the Program</h5>
In addition to
<i>yyparse()</i>
and
<i>yylex()</i>,
the functions
<i>yyerror()</i>
and
<i>main()</i>
are required to make a complete program.
The application can supply
<i>main()</i>
and
<i>yyerror()</i>,
or those routines can be obtained from the
<i>yacc</i>
library.
<h5><a name = "tag_001_014_2954_011">&nbsp;</a>Yacc Library</h5>
<xref type="5" name="yacclib"></xref>
The following functions appear only in the
<i>yacc</i>
library accessible through the
<b>-l&nbsp;y</b>
operand to
<i><a href="cc.html">cc</a></i>
or
<i><a href="c89.html">c89</a></i>;
they can therefore be redefined by a portable application:
<dl compact>

<dt><b>int main(void)</b><dd>
This function will call
<i>yyparse()</i>
and exit with an unspecified value.
Other actions within this function are unspecified.

<dt><b>int yyerror(const char *<i>s</i></b><dd>
This function
will write the NUL-terminated argument to standard error, followed by a
newline character.

</dl>
<p>
The order of the
<b>-l&nbsp;y</b>
and
<b>-l&nbsp;l</b>
operands given to
<i><a href="cc.html">cc</a></i>
or
<i><a href="c89.html">c89</a></i>
is significant;
the application must either provide its own
<i>main()</i>
function or ensure that
<b>-l&nbsp;y</b>
precedes
<b>-l&nbsp;l</b>.
<h5><a name = "tag_001_014_2954_012">&nbsp;</a>Debugging the Parser</h5>
The parser generated by
<i>yacc</i>
will have diagnostic facilities in it that can be
optionally enabled at either compile time or at run time (if enabled
at compile time).
The compilation of the runtime debugging code is under the control of
YYDEBUG,
a preprocessor symbol.
If
YYDEBUG
has a non-zero value, the debugging code will be included.
If its value is zero, the code will not be included.
<p>
In parsers where the debugging code has been included, the external
int yydebug
can be used to turn debugging on (with a non-zero value) and off (zero value)
at run time.
The initial value of
<i>yydebug</i>
will be zero.
<p>
When
<b>-t</b>
is specified,
the code file will be built such that, if
YYDEBUG
is not already defined at compilation time (using the
<i><a href="c89.html">c89</a></i>
<b>-D</b>
<b>YYDEBUG</b>
option, for example),
YYDEBUG
will be set explicitly to 1.
When
<b>-t</b>
is not specified,
the code file will be built such that, if
YYDEBUG
is not already defined, it will be set explicitly to zero.
<p>
The format of the debugging output is unspecified but
includes at least enough information to determine the shift and reduce actions,
and the input symbols.
It also provides information
about error recovery.
<h5><a name = "tag_001_014_2954_013">&nbsp;</a>Algorithms</h5>
<xref type="5" name="yaccalg"></xref>
The parser constructed by
<i>yacc</i>
implements an
LALR(1)
parsing algorithm as
documented in the literature.
It is unspecified whether the parser is table-driven
or direct-coded.
<p>
A parser generated by
<b>yacc</b>
will never request an input symbol from
<i>yylex()</i>
while in a state where the only actions other than
the error action are reductions by a single rule.
<p>
The literature of parsing theory defines these concepts.
<h5><a name = "tag_001_014_2954_014">&nbsp;</a>Limits</h5>
The
<i>yacc</i>
utility may have several internal tables.
The minimum maximums for these tables are shown in
the following table.
The exact meaning of these values is implementation-dependent.
The implementation will define the relationship between these
values and between them and any error messages that the
implementation may generate should it run out of space for any
internal structure.
An implementation may combine groups of these
resources into a single pool as long as the total available to
the user does not fall below the
sum of the sizes specified by this section.
<pre>
<table  bordercolor=#000000 border=1 align=center>
<tr valign=top><th align=center><b>Limit</b>
<th align=center><b>Minimum<br>Maximum</b>
<th align=center><b>Description</b>
<tr valign=top><td align=left>{NTERMS}
<td align=left>126
<td align=left>Number of tokens.
<tr valign=top><td align=left>{NNONTERM}
<td align=left>200
<td align=left>Number of non-terminals.
<tr valign=top><td align=left>{NPROD}
<td align=left>300
<td align=left>Number of rules.
<tr valign=top><td align=left>{NSTATES}
<td align=left>600
<td align=left>Number of states.
<tr valign=top><td align=left>{MEMSIZE}
<td align=left>5200
<td align=left> Length of rules. The total length, in names (tokens and non-terminals), of all the rules of the grammar. The left-hand side is counted for each rule, even if it is not explicitly repeated, as specified in 
<tr valign=top><td align=left>{ACTSIZE}
<td align=left>4000
<td align=left> Number of actions. &quot;Actions&quot; here (and in the description file) refer to parser actions (shift, reduce, and so on) not to semantic actions defined in 
</table>
</pre>
<h6 align=center><xref table="Internal Limits in <I>yacc</i>"></xref>Table: Internal Limits in <i>yacc</i></h6>
<p>
</blockquote><h4><a name = "tag_001_014_2955">&nbsp;</a>EXIT STATUS</h4><blockquote>
The following exit values are returned:
<dl compact>

<dt>0<dd>Successful completion.

<dt>&gt;0<dd>An error occurred.

</dl>
</blockquote><h4><a name = "tag_001_014_2956">&nbsp;</a>CONSEQUENCES OF ERRORS</h4><blockquote>
If any errors are encountered, the run is aborted and
<i>yacc</i>
exits with a non-zero status.
Partial code files and header files files may be produced.
The summary information in the description file
will always be produced if the
<b>-v</b>
flag is present.
</blockquote><h4><a name = "tag_001_014_2957">&nbsp;</a>APPLICATION USAGE</h4><blockquote>
Historical implementations experience name conflicts on the names
yacc.tmp,
yacc.acts,
yacc.debug,
y.tab.c,
y.tab.h
and
y.output
if more
than one copy of
<i>yacc</i>
is running in a single directory at one time.
The
<b>-b</b>
option was added to overcome this problem.
The related problem of allowing multiple
<i>yacc</i>
parsers to be placed in the same file was addressed
by adding a
<b>-p</b>
option to override the previously hard-coded
yy
variable prefix.
<p>
The description of the
<b>-p</b>
option specifies the minimal set of function and variable names
that cause conflict when multiple parsers are linked together.
YYSTYPE
does not need to be changed.
Instead, the programmer can use
<b>-b</b>
to give the
header files for different parsers different names, and then the file
with the
<i>yylex()</i>
for a given parser can include the header for that parser.
Names such as
<i>yyclearerr</i>
do not need to be changed because
they are used only in the actions;
they do not have linkage.
It is possible that an implementation will have other names,
either internal ones for implementing things such as
<i>yyclearerr</i>,
or providing non-standard features that it wants to change with
<b>-p</b>.
<p>
Unary operators that are the same token as a binary operator in general
need their precedence adjusted.
This is handled by the
<b>%prec</b>
advisory symbol associated with the particular grammar rule defining
that unary operator.
See
<xref href=yaccgram><a href="#tag_001_014_2954_004">
Grammar Rules in yacc
</a></xref>.
Applications are not required to use this operator for unary
operators, but the grammars that do not require it are rare.
<br>
</blockquote><h4><a name = "tag_001_014_2958">&nbsp;</a>EXAMPLES</h4><blockquote>
Access to the
<i>yacc</i>
library is obtained with library search operands to
<i><a href="cc.html">cc</a></i>
or
<i><a href="c89.html">c89</a></i>.
To use the
<i>yacc</i>
library
<i>main()</i>:
<pre>
<code>
c89 y.tab.c -l y
</code>
</pre>
<p>
Both the
<i><a href="lex.html">lex</a></i>
library and the
<i>yacc</i>
library contain
<i>main()</i>.
To access the
<i>yacc</i>
<i>main()</i>:
<pre>
<code>
c89 y.tab.c lex.yy.c -l y -l l
</code>
</pre>
<br>
This ensures that the
<i>yacc</i>
library is searched first, so that its
<i>main()</i>
is used.
<p>
The historical
<i>yacc</i>
libraries have contained two simple functions that are
normally coded by the application programmer.
These library functions are similar to the following code:
<pre>
<code>
#include &lt;locale.h&gt;
int main(void)
{
    extern int yyparse();

    setlocale(LC_ALL, "");

    /* If the following parser is one created by lex, the
       application must be careful to ensure that LC_CTYPE
       and LC_COLLATE are set to the POSIX locale.  */
    (void) yyparse();
    return (0);
}

#include &lt;stdio.h&gt;

int yyerror(const char *msg)
{
    (void) fprintf(stderr, "%s\n", msg);
    return (0);
}
</code>
</pre>
</blockquote><h4><a name = "tag_001_014_2959">&nbsp;</a>FUTURE DIRECTIONS</h4><blockquote>
The IEEE PASC 1003.2 Interpretations Committee has forwarded concerns about
parts of this interface definition to the IEEE PASC Shell and Utilities Working Group
which is identifying the corrections.
A future revision of this specification will align with
IEEE Std. 1003.2b when finalised.
</blockquote><h4><a name = "tag_001_014_2960">&nbsp;</a>SEE ALSO</h4><blockquote>
<i><a href="cc.html">cc</a></i>,
<i><a href="c89.html">c89</a></i>,
<i><a href="lex.html">lex</a></i>.
</blockquote><hr size=2 noshade>
<center><font size=2>
UNIX &reg; is a registered Trademark of The Open Group.<br>
Copyright &copy; 1997 The Open Group
<br> [ <a href="../index.html">Main Index</a> | <a href="../xshix.html">XSH</a> | <a href="../xcuix.html">XCU</a> | <a href="../xbdix.html">XBD</a> | <a href="../cursesix.html">XCURSES</a> | <a href="../xnsix.html">XNS</a> ]

</font></center><hr size=2 noshade>
</body></html>
